//
// Created by TianBo on 2022/6/5.
//

//经典dp
//优化：空间优化，直接在原grid数组上修改，不用新增dp数组

#include "iostream"
#include "vector"

using namespace std;

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size()));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.size(); ++i) {
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        for (int i = 1; i < grid[0].size(); ++i) {
            dp[0][i] = grid[0][i] + dp[0][i-1];
        }
        for (int i = 1; i < grid.size(); ++i) {
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[i][j] = max(dp[i-1][j] + grid[i][j],dp[i][j-1] + grid[i][j]);
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

int main()
{

}